package main;

import java.io.IOException;
import java.util.Collections;
import java.util.Random;

import data.Cities;
import utils.DataUtils;
import utils.EulerCycle;
import utils.HamiltonCycle;
import utils.MinimumSpanningTree;
import utils.TSPSolution;

public class LocalSearch {
    public static final int K = 100;
    TSPSolution[] s;
    TSPSolution best;
    Cities c;
    
    public LocalSearch(String file) throws NumberFormatException, IOException {
        s = new TSPSolution[K];
        c = new Cities();
        DataUtils.loadData(c, file);
        MinimumSpanningTree tree = new MinimumSpanningTree(c);
        EulerCycle euler = new EulerCycle(tree);
        HamiltonCycle hamilton = new HamiltonCycle(euler);
        System.out.println(c.getN());
        s[0] = new TSPSolution(hamilton);
        calculateCost(s[0]);
        for (int i = 1; i < K; i++) {
            s[i] = new TSPSolution(c.getN());
            calculateCost(s[i]);
        }
      best = new TSPSolution(s[0]);
    }
    
    private void calculateCost(TSPSolution tsp) {
        double cost = 0;
        for (int i = 1; i < c.getN(); i++)
            cost += c.distance(tsp.getCity(i), tsp.getCity(i + 1));
        cost += c.distance(tsp.getCity(c.getN()), tsp.getCity(1));
        tsp.setCost(cost);
    }

    @SuppressWarnings("unused")
    private void display() {
        for (int i = 0; i < K; i++) {
            s[i].display();
            System.out.println("--------------------------------------------------");
        }
    }
    
    private void firstMove(TSPSolution start) {
        long startTime, endTime, timeLimit;
        startTime = System.currentTimeMillis();
        timeLimit = 3 * 60 * 1000;
        Random rand = new Random();
        while (true) {
//            int nIterator = 100 + rand.nextInt(100);
            int nIterator = 10000;
            boolean found = false;
            for (int j = 0; j < nIterator; j++) {
                int post, node;                    
                post = 2 + rand.nextInt(c.getN() - 2);
                node = start.getCity(post);
                for (int k = 2; k < c.getN(); k++) {
                    double cost = start.getCost();
                    if (k != post && Math.abs(k - post) != 1) {
                        cost -=   c.distance(start.getCity(post - 1), start.getCity(post))
                                + c.distance(start.getCity(post), start.getCity(post + 1))
                                + c.distance(start.getCity(k), start.getCity(k - 1))
                                - c.distance(start.getCity(post - 1), start.getCity(post + 1))
                                - c.distance(start.getCity(k - 1), start.getCity(post))
                                - c.distance(start.getCity(post), start.getCity(k));
                        if (cost < start.getCost()) {
                            for (int h = post; h < c.getN(); h++)
                                start.setCity(h, start.getCity(h + 1));
                            int k_ = k < post ? k : k-1;
                            for (int h = c.getN(); h > k_; h--)
                                start.setCity(h, start.getCity(h - 1));
                            start.setCity(k_, node);
                            start.setCost(cost);
                            found = true;
                            break;
                        }
                    }
                }
                
                int u, v, nodeU, nodeV;
                u = 2 + rand.nextInt(c.getN() - 2);
                v = 2 + rand.nextInt(c.getN() - 2);
                nodeU = start.getCity(u);
                nodeV = start.getCity(v);
                if (u != v) {
                    double cost = start.getCost();
                    if (Math.abs(u - v) != 1) {
                        cost -=   c.distance(start.getCity(u), start.getCity(u - 1))
                                + c.distance(start.getCity(u), start.getCity(u + 1))
                                + c.distance(start.getCity(v), start.getCity(v - 1))
                                + c.distance(start.getCity(v), start.getCity(v + 1))
                                - c.distance(start.getCity(v), start.getCity(u + 1))
                                - c.distance(start.getCity(v), start.getCity(u - 1))
                                - c.distance(start.getCity(u), start.getCity(v + 1))
                                - c.distance(start.getCity(u), start.getCity(v - 1));
                    } else {
                        int min = Math.min(u, v);
                        int max = Math.max(u, v);
                        cost -=   c.distance(start.getCity(min - 1), start.getCity(min))
                                + c.distance(start.getCity(max), start.getCity(max + 1))
                                - c.distance(start.getCity(min - 1), start.getCity(max))
                                - c.distance(start.getCity(max + 1), start.getCity(min));
                    }
                    if (cost < start.getCost()) {
                        start.setCity(u, nodeV);
                        start.setCity(v, nodeU);
                        start.setCost(cost);
                        found = true;
                    }

                }
                u = 2 + rand.nextInt(c.getN() - 2);
                v = 2 + rand.nextInt(c.getN() - 2);
                if (u != v) {
                    double cost = start.getCost();
                    int min = Math.min(u, v);
                    int max = Math.max(u, v);
                    cost -=   c.distance(start.getCity(min - 1), start.getCity(min))
                            + c.distance(start.getCity(max), start.getCity(max + 1))
                            - c.distance(start.getCity(min - 1), start.getCity(max))
                            - c.distance(start.getCity(max + 1), start.getCity(min));
                    if (cost < start.getCost()) {
                        int[] arr = new int[max - min + 2];
                        for (int ii = min; ii <= max; ii++)
                            arr[ii - min] = start.getCity(ii); 
                        for (int ii = min; ii <= max; ii++)
                            start.setCity(ii, arr[max - ii]);
                        start.setCost(cost);
                        found = true;
                    }
                }
                
                u = 2 + rand.nextInt(c.getN() - 2);
                v = 2 + rand.nextInt(c.getN() - 2);
                if (Math.abs(u - v) > 1) {
                    double cost = start.getCost();
                    int min = Math.min(u, v);
                    int max = Math.max(u, v);
                    cost -=   c.distance(start.getCity(min), start.getCity(min + 1))
                            + c.distance(start.getCity(max), start.getCity(max + 1))
                            - c.distance(start.getCity(min), start.getCity(max))
                            - c.distance(start.getCity(min + 1), start.getCity(max + 1));
                    if (cost < start.getCost()) {
                        min++;
                        int[] arr = new int[max - min + 2];
                        for (int ii = min; ii <= max; ii++)
                            arr[ii - min] = start.getCity(ii); 
                        for (int ii = min; ii <= max; ii++)
                            start.setCity(ii, arr[max - ii]);                        
                        start.setCost(cost);
                        found = true;
                    }                    
                }                
            }    
            if (!found)
                break;
            endTime = System.currentTimeMillis();
            if (endTime - startTime > timeLimit)
                return;
        }        
    }
    
    private void secondMove(TSPSolution start) {
        long startTime, endTime, timeLimit;
        startTime = System.currentTimeMillis();
        timeLimit = 30 * 60 * 1000;
        Random rand = new Random();
        while (true) {
            int nIterator = 100 + rand.nextInt(100);
            boolean found = false;
            for (int post = 2; post < c.getN() - 1; post++) {
                int node;                    
                node = start.getCity(post);
                for (int k = 2; k < c.getN(); k++) {
                    double cost = start.getCost();                    
                    if (k != post && Math.abs(k - post) != 1) {
                        cost -=   c.distance(start.getCity(post - 1), start.getCity(post))
                                + c.distance(start.getCity(post), start.getCity(post + 1))
                                + c.distance(start.getCity(k), start.getCity(k - 1))
                                - c.distance(start.getCity(post - 1), start.getCity(post + 1))
                                - c.distance(start.getCity(k - 1), start.getCity(post))
                                - c.distance(start.getCity(post), start.getCity(k));
                        if (cost < start.getCost()) {
                            for (int h = post; h < c.getN(); h++)
                                start.setCity(h, start.getCity(h + 1));
                            int k_ = k < post ? k : k-1;
                            for (int h = c.getN(); h > k_; h--)
                                start.setCity(h, start.getCity(h - 1));
                            start.setCity(k_, node);
                            start.setCost(cost);
                            found = true;
                            break;
                        }
                    }
                }
                if (found)
                    break;
            }    
            if (!found)
                break;
            endTime = System.currentTimeMillis();
            if (endTime - startTime > timeLimit)
                return;
        }                
    }
    
    private void approachLocalSearch() {        
        for (int i = 0; i < K; i++) {
            TSPSolution start = new TSPSolution(s[i]);
            firstMove(start);
            if (start.getCost() < best.getCost())
                best = new TSPSolution(start);
        }
    }
    
    public void run() {
        System.out.println("tsp approximation ratio 2: " + Math.round(s[0].getCost()));
        approachLocalSearch();
        System.out.println("Best Solution: " + Math.round(best.getCost()));
        for (int i = 1; i <= c.getN(); i++)
            System.out.print(best.getCity(i) + " ");
        System.out.println();
        
    }
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        LocalSearch test = new LocalSearch("instances/rat195.tsp");
        test.run();
    }    
}
